<!DOCTYPE html>
<html class="no-js" lang="zh">
  <head>
<meta charset="utf-8">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1">
<meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
<link rel="alternate" href="https://www.desgard.com" hreflang="pt-BR">
<link href="http://gmpg.org/xfn/11" rel="profile">
<meta name="HandheldFriendly" content="True">
<meta name="MobileOptimized" content="320">
<meta name="theme-color" content="#005344">
<title>Guardia · 瓜地</title>
<meta name="google-site-verification" content="zS1dSn20XtA4FJYEOQLXqI0boxZdMnJ2g3beje-cl20">
<meta name="description" content="I write many code to write less code.💻">
<meta name="keywords" content="">
<!-- Social: Facebook / Open Graph -->
<meta property="og:url" content="https://www.desgard.com/lazy-segment-tree/">
<meta property="og:title" content="       用 Lazy 思想实现 Segment Tree 的区间更新 | Gua  ">
<meta property="og:description" content="I write many code to write less code.💻">
<meta property="og:site_name" content="Desgard_Duan">
<meta property="og:locale" content="pt_BR">
<meta property="og:type" content="website">
<meta property="og:author" content="https://www.facebook.com/desgard.duan">
<meta property="og:image" content="https://www.desgard.com">
<!-- Social: Twitter -->
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:site" content="@nandomoreirame">
<meta name="twitter:domain" content="https://www.desgard.com">
<meta name="twitter:title" content="       用 Lazy 思想实现 Segment Tree 的区间更新 | Gua  ">
<meta name="twitter:description" content="I write many code to write less code.💻">
<meta name="twitter:image:src" content="https://www.desgard.com">
<!-- Favicons -->
<link rel="apple-touch-icon" sizes="114x114" href="https://www.desgard.com/assets/ico/apple-touch-icon-114-516f4e19976b9e4dbb77ad9b576831fe.png">
<link rel="apple-touch-icon" sizes="72x72" href="https://www.desgard.com/assets/ico/apple-touch-icon-72-5409b2df229305703caf583d86c845ab.png">
<link rel="apple-touch-icon" href="https://www.desgard.com/assets/ico/apple-touch-icon-57-aa873e019cf659e0d4e6a0b5bb9f379d.png">
<link rel="shortcut icon" href="https://www.desgard.com/assets/ico/favicon-4298be3d3fbe23e18d65bded9d930899.png">
<!-- rel prev and next -->
<!-- Canonical link tag -->
<link rel="canonical" href="https://www.desgard.com/lazy-segment-tree/">
<link rel="alternate" type="application/rss+xml" title="Gua" href="https://www.desgard.com/feed.xml">
<link rel="stylesheet" href="/assets/main-0b7b828712f4c43b75bba4861c907bb1.css">
<script src="/assets/modernizr-custom-cb807611a3e262b2eac59444cbab74d6.js" data-cfasync="false"></script>
<script src="/assets/js/jquery-3.1.js"></script>
<script src="/assets/js/jquery.rotate.js"></script>
<script type="text/javascript" src="https://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script type="application/ld+json">
{
  "@context": "http://schema.org",
  "@type": "Website",
  "publisher": "www.desgard.com",
  "url": "http://www.desgard.com/",
  "description": "瓜地"
}
</script>
<script type="text/javascript">
  var disqus_shortname = 'desgard',
      baseurl          = '';
</script>
<!--
<script type="text/javascript">
var _gaq = _gaq || [];
_gaq.push(['_setAccount', 'UA-52446115-1']);
_gaq.push(['_trackPageview']);
(function() {
  var ga = document.createElement('script'); ga.type = 'text/javascript'; ga.async = true;
  ga.src = ('https:' == document.location.protocol ? 'https://ssl' : 'http://www') + '.google-analytics.com/ga.js';
  var s = document.getElementsByTagName('script')[0]; s.parentNode.insertBefore(ga, s);
})();
</script>-->
<script>
var _hmt = _hmt || [];
(function() {
  var hm = document.createElement("script");
  hm.src = "//hm.baidu.com/hm.js?c5a8123bc51782a3083a631ed9ff50e4";
  var s = document.getElementsByTagName("script")[0]; 
  s.parentNode.insertBefore(hm, s);
})();
</script>
<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
      tex2jax: {
        inlineMath: [ ['$','$'] ],
        displayMath: [ ['$$','$$'] ],
        processEscapes: true
      }
    });
  </script>
  </head>
  <body class="post-template single">
    <header class="header">
  <div class="container">
    <h1><a href="/"><strong>desgard</strong>.com</a></h1>
    <nav class="navbar">
      <ul>
        <li><a href="/">Home</a></li>
        <li><a href="#!" data-modal="modalSearch"><i class="fa fa-search"></i></a></li>
        <li><a href="/comment " target="_blank"><i class="fa fa-comments"></i></a></li>
        <li><a href="/feed.xml" target="_blank"><i class="fa fa-feed"></i></a></li>
      </ul>
    </nav>
  </div>
</header>
    <main class="wrapper container" itemprop="mainContentOfPage" itemscope="itemscope" itemtype="http://schema.org/Blog">
      <article class="post" itemscope="itemscope" itemtype="http://schema.org/BlogPosting" itemprop="blogPost">
  <header class="post-header">
    <h1>用 Lazy 思想实现 Segment Tree 的区间更新</h1>
    <div class="post-meta">
      <time datetime="2015-10-13">
        <i class="fa fa-calendar-o"></i> <time datetime="2017-08-27"> 2017-08-27
      </time>
      <span>
        <i class="fa fa-comments"></i> <a href="#container">Comment me!</a>
      </span>
      <span>
<!--
        <i class="fa fa-folder-open-o"></i> 
-->
      </span>
    </div>
  </header>
  <blockquote>
  <p>这篇文章是向 <strong>Ray Wenderlich</strong> 中 <strong>Swift Algorithm Club</strong> 的投稿文。用来讲述 <code>Segment Tree</code> 的区间更新操作以及 Swift 实现方案。<strong><a href="https://github.com/raywenderlich/swift-algorithm-club/issues/591">Open Issue #591</a></strong></p>
</blockquote>
<p>在原始的实现中，<strong>Artur Antonov</strong> 利用 Swift 中很优雅的泛型<code>&lt;T&gt;</code>方式来对 Segment Tree 这个数据结构进行了实现。并且在这个实现中可以对其传递一个 <code>function: (T, T) -&gt; T</code> 来反映两个叶子节点对父节点的影响。并且泛型的优势体现在可以用 Segment Tree 来解决字符串的问题，就像 Playground 中最后的这个例子：</p>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="n">stringSegmentTree</span><span class="o">.</span><span class="n">replaceItem</span><span class="p">(</span><span class="ss">at</span><span class="p">:</span> <span class="mi">0</span><span class="p">,</span> <span class="ss">withItem</span><span class="p">:</span> <span class="s2">&quot;I&quot;</span><span class="p">)</span>
<span class="n">stringSegmentTree</span><span class="o">.</span><span class="n">replaceItem</span><span class="p">(</span><span class="ss">at</span><span class="p">:</span> <span class="mi">1</span><span class="p">,</span> <span class="ss">withItem</span><span class="p">:</span> <span class="s2">&quot; like&quot;</span><span class="p">)</span>
<span class="n">stringSegmentTree</span><span class="o">.</span><span class="n">replaceItem</span><span class="p">(</span><span class="ss">at</span><span class="p">:</span> <span class="mi">2</span><span class="p">,</span> <span class="ss">withItem</span><span class="p">:</span> <span class="s2">&quot; algorithms&quot;</span><span class="p">)</span>
<span class="n">stringSegmentTree</span><span class="o">.</span><span class="n">replaceItem</span><span class="p">(</span><span class="ss">at</span><span class="p">:</span> <span class="mi">3</span><span class="p">,</span> <span class="ss">withItem</span><span class="p">:</span> <span class="s2">&quot; and&quot;</span><span class="p">)</span>
<span class="n">stringSegmentTree</span><span class="o">.</span><span class="n">replaceItem</span><span class="p">(</span><span class="ss">at</span><span class="p">:</span> <span class="mi">4</span><span class="p">,</span> <span class="ss">withItem</span><span class="p">:</span> <span class="s2">&quot; swift&quot;</span><span class="p">)</span>
<span class="n">stringSegmentTree</span><span class="o">.</span><span class="n">replaceItem</span><span class="p">(</span><span class="ss">at</span><span class="p">:</span> <span class="mi">5</span><span class="p">,</span> <span class="ss">withItem</span><span class="p">:</span> <span class="s2">&quot;!&quot;</span><span class="p">)</span>
<span class="nb">print</span><span class="p">(</span><span class="n">stringSegmentTree</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="ss">leftBound</span><span class="p">:</span> <span class="mi">0</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="mi">5</span><span class="p">))</span>
<span class="sr">//</span> <span class="s2">&quot;I like algorithms and swift!&quot;</span></code></pre></div>
<p><code>&lt;T&gt;</code> 这种方式固然有趣，可以利用 Segment Tree 来做字符串处理的地方真的少之又少。况且此数据结构的出现源自于<em>区间性处理问题</em>，将一维集合通过分制思想多线段划分，从而以空间换时间达到高效操作的数据结构。而最常见的问题即为解决区间内任意子区间求和的问题。从原本 <code>O(n)</code> 时间复杂度以二分查询的形式降低为 <code>O(logn)</code>，达到高效查询。</p>
<h2 id="pushup-">pushUp 向下递归，向上更新操作</h2>
<p>我们可以参考一下 <strong>Artur Antonov</strong> 的实现方法，其中有建树、单点更新和区间查询三种操作。这里将 Segment Tree 的建树操作和单点更新拿出来看一下：</p>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="kp">public</span> <span class="n">init</span><span class="p">(</span><span class="ss">array</span><span class="p">:</span> <span class="o">[</span><span class="n">T</span><span class="o">]</span><span class="p">,</span> <span class="ss">leftBound</span><span class="p">:</span> <span class="no">Int</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="no">Int</span><span class="p">,</span> <span class="ss">function</span><span class="p">:</span> <span class="vi">@escaping</span> <span class="p">(</span><span class="n">T</span><span class="p">,</span> <span class="n">T</span><span class="p">)</span> <span class="o">-&gt;</span> <span class="n">T</span><span class="p">)</span> <span class="p">{</span>
	<span class="nb">self</span><span class="o">.</span><span class="n">leftBound</span> <span class="o">=</span> <span class="n">leftBound</span>
	<span class="nb">self</span><span class="o">.</span><span class="n">rightBound</span> <span class="o">=</span> <span class="n">rightBound</span>
	<span class="nb">self</span><span class="o">.</span><span class="n">function</span> <span class="o">=</span> <span class="n">function</span>
	<span class="sr">//</span> <span class="err">①</span>
	<span class="k">if</span> <span class="n">leftBound</span> <span class="o">==</span> <span class="n">rightBound</span> <span class="p">{</span>
		<span class="n">value</span> <span class="o">=</span> <span class="n">array</span><span class="o">[</span><span class="n">leftBound</span><span class="o">]</span>
	<span class="p">}</span> 
	<span class="sr">//</span> <span class="err">②</span>
	<span class="k">else</span> <span class="p">{</span>
		<span class="n">let</span> <span class="n">middle</span> <span class="o">=</span> <span class="p">(</span><span class="n">leftBound</span> <span class="o">+</span> <span class="n">rightBound</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span>
		<span class="n">leftChild</span> <span class="o">=</span> <span class="no">SegmentTree</span><span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;</span><span class="p">(</span><span class="ss">array</span><span class="p">:</span> <span class="n">array</span><span class="p">,</span> <span class="ss">leftBound</span><span class="p">:</span> <span class="n">leftBound</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="n">middle</span><span class="p">,</span> <span class="ss">function</span><span class="p">:</span> <span class="n">function</span><span class="p">)</span>
		<span class="n">rightChild</span> <span class="o">=</span> <span class="no">SegmentTree</span><span class="o">&lt;</span><span class="n">T</span><span class="o">&gt;</span><span class="p">(</span><span class="ss">array</span><span class="p">:</span> <span class="n">array</span><span class="p">,</span> <span class="ss">leftBound</span><span class="p">:</span> <span class="n">middle</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="n">rightBound</span><span class="p">,</span> <span class="ss">function</span><span class="p">:</span> <span class="n">function</span><span class="p">)</span>
		<span class="n">value</span> <span class="o">=</span> <span class="n">function</span><span class="p">(</span><span class="n">leftChild!</span><span class="o">.</span><span class="n">value</span><span class="p">,</span> <span class="n">rightChild!</span><span class="o">.</span><span class="n">value</span><span class="p">)</span>
	<span class="p">}</span>
<span class="p">}</span></code></pre></div>
<p>在 ① 位置中，当遍历节点的左边极限范围和右边极限范围相同时，则说明这是一个叶子节点，则直接为其赋值即可。而 ② 位置说明该节点为父节点（仅对于有无子节点而言）时，需要对下层叶子继续构建，在后续的递归过程时对该节点进行构建。</p>
<p>继而，我们来看单点更新(Query)的操作：</p>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="kp">public</span> <span class="n">func</span> <span class="n">query</span><span class="p">(</span><span class="ss">leftBound</span><span class="p">:</span> <span class="no">Int</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="no">Int</span><span class="p">)</span> <span class="o">-&gt;</span> <span class="n">T</span> <span class="p">{</span>
	<span class="k">if</span> <span class="nb">self</span><span class="o">.</span><span class="n">leftBound</span> <span class="o">==</span> <span class="n">leftBound</span> <span class="o">&amp;&amp;</span> <span class="nb">self</span><span class="o">.</span><span class="n">rightBound</span> <span class="o">==</span> <span class="n">rightBound</span> <span class="p">{</span>
		<span class="k">return</span> <span class="nb">self</span><span class="o">.</span><span class="n">value</span>
	<span class="p">}</span>
	<span class="n">guard</span> <span class="n">let</span> <span class="n">leftChild</span> <span class="o">=</span> <span class="n">leftChild</span> <span class="k">else</span> <span class="p">{</span> <span class="n">fatalError</span><span class="p">(</span><span class="s2">&quot;leftChild should not be nil&quot;</span><span class="p">)</span> <span class="p">}</span>
	<span class="n">guard</span> <span class="n">let</span> <span class="n">rightChild</span> <span class="o">=</span> <span class="n">rightChild</span> <span class="k">else</span> <span class="p">{</span> <span class="n">fatalError</span><span class="p">(</span><span class="s2">&quot;rightChild should not be nil&quot;</span><span class="p">)</span> <span class="p">}</span>
	<span class="sr">//</span> <span class="err">①</span>
	<span class="k">if</span> <span class="n">leftChild</span><span class="o">.</span><span class="n">rightBound</span> <span class="o">&lt;</span> <span class="n">leftBound</span> <span class="p">{</span>
		<span class="k">return</span> <span class="n">rightChild</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="ss">leftBound</span><span class="p">:</span> <span class="n">leftBound</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="n">rightBound</span><span class="p">)</span>
	<span class="p">}</span> 
	<span class="sr">//</span> <span class="err">②</span>
	<span class="k">else</span> <span class="k">if</span> <span class="n">rightChild</span><span class="o">.</span><span class="n">leftBound</span> <span class="o">&gt;</span> <span class="n">rightBound</span> <span class="p">{</span>
		<span class="k">return</span> <span class="n">leftChild</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="ss">leftBound</span><span class="p">:</span> <span class="n">leftBound</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="n">rightBound</span><span class="p">)</span>
	<span class="p">}</span>
	<span class="sr">//</span> <span class="err">③</span> 
	<span class="k">else</span> <span class="p">{</span>
		<span class="n">let</span> <span class="n">leftResult</span> <span class="o">=</span> <span class="n">leftChild</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="ss">leftBound</span><span class="p">:</span> <span class="n">leftBound</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="n">leftChild</span><span class="o">.</span><span class="n">rightBound</span><span class="p">)</span>
		<span class="n">let</span> <span class="n">rightResult</span> <span class="o">=</span> <span class="n">rightChild</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="ss">leftBound</span><span class="p">:</span><span class="n">rightChild</span><span class="o">.</span><span class="n">leftBound</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="n">rightBound</span><span class="p">)</span>
		<span class="k">return</span> <span class="n">function</span><span class="p">(</span><span class="n">leftResult</span><span class="p">,</span> <span class="n">rightResult</span><span class="p">)</span>
	<span class="p">}</span>
<span class="p">}</span></code></pre></div>
<p>在 ① 位置中是查询位置的左边界在当前节点的右边界，这时候说明击中范围偏右，需要继续向右递归查询。② 位置的情况和 ① 的情况相反，继续想左递归查询即可。而 ③ 中的代码说明当前位置为需查询位置，则继续向下递归查询，直到为单值或是恰好卡中区间即可返回结果。</p>
<p><img src="../assets/images/blog/15034809922428/pushUp.png" alt="pushUp" /></p>
<p>从上述两个代码中，我们发现这么一个共有的部分，就是<strong>向下递归，向上更新</strong>部分。其实，我们完全可以将这个向下更新的操作分离处理，当需要的时候调用即可。以下是 <code>func pushUp(lson: LazySegmentTree, rson: LazySegmentTree)</code> 操作：</p>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="sr">//</span> <span class="ss">MARK</span><span class="p">:</span> <span class="o">-</span> <span class="no">Push</span> <span class="no">Up</span> <span class="no">Operation</span>
<span class="sr">//</span> <span class="ss">Description</span><span class="p">:</span> <span class="err">这里是</span> <span class="n">push</span> <span class="n">up</span> <span class="err">操作，用来对</span> <span class="no">Segment</span> <span class="no">Tree</span> <span class="err">向上更新</span>
<span class="kp">private</span> <span class="n">func</span> <span class="n">pushUp</span><span class="p">(</span><span class="ss">lson</span><span class="p">:</span> <span class="no">LazySegmentTree</span><span class="p">,</span> <span class="ss">rson</span><span class="p">:</span> <span class="no">LazySegmentTree</span><span class="p">)</span> <span class="p">{</span>
    <span class="nb">self</span><span class="o">.</span><span class="n">value</span> <span class="o">=</span> <span class="n">lson</span><span class="o">.</span><span class="n">value</span> <span class="o">+</span> <span class="n">rson</span><span class="o">.</span><span class="n">value</span>
<span class="p">}</span></code></pre></div>
<p>以上代码中，仅仅对 <code>SumSegmentTree</code> 进行了实现，即求和线段树。有了这个方法，我们队构建和单点替换操作就可以直接调用实现。示例代码如下：</p>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="kp">public</span> <span class="n">init</span><span class="p">(</span><span class="ss">array</span><span class="p">:</span> <span class="o">[</span><span class="no">Int</span><span class="o">]</span><span class="p">,</span> <span class="ss">leftBound</span><span class="p">:</span> <span class="no">Int</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="no">Int</span><span class="p">)</span> <span class="p">{</span>
    <span class="nb">self</span><span class="o">.</span><span class="n">leftBound</span> <span class="o">=</span> <span class="n">leftBound</span>
    <span class="nb">self</span><span class="o">.</span><span class="n">rightBound</span> <span class="o">=</span> <span class="n">rightBound</span>
    <span class="nb">self</span><span class="o">.</span><span class="n">value</span> <span class="o">=</span> <span class="mi">0</span>
    <span class="nb">self</span><span class="o">.</span><span class="n">lazyValue</span> <span class="o">=</span> <span class="mi">0</span>
    <span class="k">if</span> <span class="n">leftBound</span> <span class="o">==</span> <span class="n">rightBound</span> <span class="p">{</span>
        <span class="n">value</span> <span class="o">=</span> <span class="n">array</span><span class="o">[</span><span class="n">leftBound</span><span class="o">]</span>
        <span class="k">return</span>
    <span class="p">}</span>
    <span class="n">let</span> <span class="n">middle</span> <span class="o">=</span> <span class="p">(</span><span class="n">leftBound</span> <span class="o">+</span> <span class="n">rightBound</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span>
    <span class="n">leftChild</span> <span class="o">=</span> <span class="no">LazySegmentTree</span><span class="p">(</span><span class="ss">array</span><span class="p">:</span> <span class="n">array</span><span class="p">,</span> <span class="ss">leftBound</span><span class="p">:</span> <span class="n">leftBound</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="n">middle</span><span class="p">)</span>
    <span class="n">rightChild</span> <span class="o">=</span> <span class="no">LazySegmentTree</span><span class="p">(</span><span class="ss">array</span><span class="p">:</span> <span class="n">array</span><span class="p">,</span> <span class="ss">leftBound</span><span class="p">:</span> <span class="n">middle</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="n">rightBound</span><span class="p">)</span>
    <span class="n">pushUp</span><span class="p">(</span><span class="ss">lson</span><span class="p">:</span> <span class="n">leftChild!</span><span class="p">,</span> <span class="ss">rson</span><span class="p">:</span> <span class="n">rightChild!</span><span class="p">)</span>
<span class="p">}</span>
<span class="sr">//</span> <span class="ss">MARK</span><span class="p">:</span> <span class="o">-</span> <span class="no">One</span> <span class="no">Item</span> <span class="no">Update</span>
<span class="kp">public</span> <span class="n">func</span> <span class="n">update</span><span class="p">(</span><span class="ss">index</span><span class="p">:</span> <span class="no">Int</span><span class="p">,</span> <span class="ss">newValue</span><span class="p">:</span> <span class="no">Int</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="nb">self</span><span class="o">.</span><span class="n">leftBound</span> <span class="o">==</span> <span class="nb">self</span><span class="o">.</span><span class="n">rightBound</span> <span class="p">{</span>
        <span class="nb">self</span><span class="o">.</span><span class="n">value</span> <span class="o">=</span> <span class="n">newValue</span>
        <span class="k">return</span>
    <span class="p">}</span>
    <span class="n">guard</span> <span class="n">let</span> <span class="n">leftChild</span>  <span class="o">=</span> <span class="n">leftChild</span>  <span class="k">else</span> <span class="p">{</span> <span class="n">fatalError</span><span class="p">(</span><span class="s2">&quot;leftChild should not be nil&quot;</span><span class="p">)</span> <span class="p">}</span>
    <span class="n">guard</span> <span class="n">let</span> <span class="n">rightChild</span> <span class="o">=</span> <span class="n">rightChild</span> <span class="k">else</span> <span class="p">{</span> <span class="n">fatalError</span><span class="p">(</span><span class="s2">&quot;rightChild should not be nil&quot;</span><span class="p">)</span> <span class="p">}</span>
    <span class="n">let</span> <span class="n">middle</span> <span class="o">=</span> <span class="p">(</span><span class="nb">self</span><span class="o">.</span><span class="n">leftBound</span> <span class="o">+</span> <span class="nb">self</span><span class="o">.</span><span class="n">rightBound</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span>
    <span class="k">if</span> <span class="n">index</span> <span class="o">&lt;=</span> <span class="n">middle</span> <span class="p">{</span> <span class="n">leftChild</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="ss">index</span><span class="p">:</span> <span class="n">index</span><span class="p">,</span> <span class="ss">newValue</span><span class="p">:</span> <span class="n">newValue</span><span class="p">)</span> <span class="p">}</span>
    <span class="k">else</span> <span class="p">{</span> <span class="n">rightChild</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="ss">index</span><span class="p">:</span> <span class="n">index</span><span class="p">,</span> <span class="ss">newValue</span><span class="p">:</span> <span class="n">newValue</span><span class="p">)</span> <span class="p">}</span>
    <span class="n">pushUp</span><span class="p">(</span><span class="ss">lson</span><span class="p">:</span> <span class="n">leftChild</span><span class="p">,</span> <span class="ss">rson</span><span class="p">:</span> <span class="n">rightChild</span><span class="p">)</span>
<span class="p">}</span></code></pre></div>
<h2 id="pushdown--lazy-">从 pushDown 操作到使用 Lazy 思想对区间进行更新</h2>
<p>上文中对于 <code>pushUp</code> 操作也许你会觉得其实没有多少变化。其实是为了引入接下来要说的 <code>pushDown</code>，进行相对而言的。</p>
<p>但是我想先来聊聊区间操作。所谓区间操作就是对集合中连续的一系列数据进行更新操作。在 <strong>Artur Antonov</strong> 的代码中，并没有实现这个操作，但是我们可以直接想到，通过一个 <code>for</code> 循环就可完成对于一个区间进行更新：</p>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="sr">//</span> <span class="ss">Sample</span><span class="p">:</span> <span class="err">对集合下标</span> <span class="o">[</span><span class="mi">2</span><span class="p">,</span> <span class="mi">5</span><span class="o">]</span> <span class="err">的数据进行更新</span>
<span class="k">for</span> <span class="n">index</span> <span class="k">in</span> <span class="mi">2</span> <span class="o">.</span><span class="n">.</span><span class="o">.</span> <span class="mi">5</span> <span class="p">{</span>
    <span class="n">sumSegmentTree</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="ss">index</span><span class="p">:</span> <span class="n">index</span><span class="p">,</span> <span class="ss">incremental</span><span class="p">:</span> <span class="mi">3</span><span class="p">)</span>
<span class="p">}</span></code></pre></div>
<p>可是这要就会存在一个 <code>O(n)</code> 复杂度的遍历，最后使得区间更新操作的时间复杂度为 <code>O(nlogn)</code>。那么有没有一种方法，将其优化至 <code>O(logn)</code>，从而使其和单点更新以及范围查询两个操作一样优美呢？</p>
<p>考虑这个问题，我们需要重新来审视线段树的这个结构：</p>
<p><img src="../assets/images/blog/15034809922428/Segment-tree.png" alt="Segment-tree" /></p>
<p>而在代码中，我们只能拿到这棵线段树的根节点。如果我们想深入到底层，然后再对树从最底层的叶子节点进行 <code>pushUp</code> 向上更新这样就能完成当前目标了，这样就要求先对这棵二叉树进行一次遍历。但一次遍历可不是易事，无论是先序还是后序，无论 DFS 还是 BFS，找到每个叶子节点一定是需要 <code>O(n)</code> 的复杂度，这已经超出了我们的期望。</p>
<p>所以我们开始考虑 <code>pushDown</code> 向下更新这种新操作，我们<strong>在大范围的父内对数据进行更新，然后再向下递归时，根据更新要求，再对叶子节点进行更新</strong>就好了。但是，这好像与 <code>pushUp</code> 没有什么改善，整棵树更新完也需要 <code>O(n)</code> 的复杂度。继续思考，当我们做范围查询操作时，也是从根节点开始，向下去卡区间范围进行递归查询。既然查询和更新的方向是一致的，我们就可以带着更新来查询了不是吗？😁 举个例子：</p>
<p><img src="../assets/images/blog/15034809922428/lazy-sample-2.png" alt="lazy-sample-2" /></p>
<p><code>update</code> 操作是为了让下标为 1 到 3 这三个元素的值加 2，所以我们在 2 层的第一个节点和 3 层第三个节点中加入 lazy 标记，代表这些节点需要更新，并在这个过程中，由于我们无需在 root 节点增加标记，所以在递归之前执行一次 <code>pushDown</code> 操作来更新 root 节点的值。</p>
<p><code>query</code> 操作时为了查询第一个元素，我们逐层递归遍历，当来到 2 层第一个节点的时候发现，这个节点 lazy 标记不为空，所以更新一下它的值，来到 3 层第一个节点时也相同，更新之后查出结果。</p>
<p>是的，这就是 <strong>Lazy 思想</strong>。<strong>当需要更新时，我们只对指定范围的父亲节点中增加一个待更新标记，说明这些范围我们需要更新。而在查询的时候，如果发现这些标记，则再对其子节点进行更新</strong>。而这个向下更新操作就是 <code>pushDown</code> 方法。</p>
<p>下面我们用 <code>Swift</code> 来实现一下这个方案，其案例是对于 <code>SumSegmentTree</code> 的完整代码：</p>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="kp">public</span> <span class="k">class</span> <span class="nc">LazySegmentTree</span> <span class="p">{</span>
    <span class="kp">private</span> <span class="n">var</span> <span class="ss">value</span><span class="p">:</span> <span class="no">Int</span>
    <span class="kp">private</span> <span class="n">var</span> <span class="ss">leftBound</span><span class="p">:</span> <span class="no">Int</span>
    <span class="kp">private</span> <span class="n">var</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="no">Int</span>
    <span class="kp">private</span> <span class="n">var</span> <span class="ss">leftChild</span><span class="p">:</span> <span class="no">LazySegmentTree</span><span class="p">?</span>
    <span class="kp">private</span> <span class="n">var</span> <span class="ss">rightChild</span><span class="p">:</span> <span class="no">LazySegmentTree</span><span class="p">?</span>
    <span class="sr">//</span> <span class="no">Interval</span> <span class="no">Update</span> <span class="no">Lazy</span> <span class="no">Element</span>
    <span class="kp">private</span> <span class="n">var</span> <span class="ss">lazyValue</span><span class="p">:</span> <span class="no">Int</span>
    <span class="sr">//</span> <span class="ss">MARK</span><span class="p">:</span> <span class="o">-</span> <span class="no">Push</span> <span class="no">Up</span> <span class="no">Operation</span>
    <span class="sr">//</span> <span class="ss">Description</span><span class="p">:</span> <span class="err">这里是</span> <span class="n">push</span> <span class="n">up</span> <span class="err">操作，用来对</span> <span class="no">Segment</span> <span class="no">Tree</span> <span class="err">向上更新</span>
    <span class="kp">private</span> <span class="n">func</span> <span class="n">pushUp</span><span class="p">(</span><span class="ss">lson</span><span class="p">:</span> <span class="no">LazySegmentTree</span><span class="p">,</span> <span class="ss">rson</span><span class="p">:</span> <span class="no">LazySegmentTree</span><span class="p">)</span> <span class="p">{</span>
        <span class="nb">self</span><span class="o">.</span><span class="n">value</span> <span class="o">=</span> <span class="n">lson</span><span class="o">.</span><span class="n">value</span> <span class="o">+</span> <span class="n">rson</span><span class="o">.</span><span class="n">value</span>
    <span class="p">}</span>
    <span class="sr">//</span> <span class="ss">MARK</span><span class="p">:</span> <span class="o">-</span> <span class="no">Push</span> <span class="no">Down</span> <span class="no">Operation</span>
    <span class="sr">//</span> <span class="ss">Description</span><span class="p">:</span> <span class="err">这里是</span> <span class="n">push</span> <span class="n">down</span> <span class="err">操作，用来对</span> <span class="no">Segment</span> <span class="no">Tree</span> <span class="err">向下更新</span>
    <span class="sr">//</span> <span class="no">Open</span> <span class="no">Interface</span> <span class="ss">Function</span><span class="p">:</span> <span class="err">此处应该开放方法对齐进行</span> <span class="no">Override</span>
    <span class="kp">private</span> <span class="n">func</span> <span class="n">pushDown</span><span class="p">(</span><span class="ss">round</span><span class="p">:</span> <span class="no">Int</span><span class="p">,</span> <span class="ss">lson</span><span class="p">:</span> <span class="no">LazySegmentTree</span><span class="p">,</span> <span class="ss">rson</span><span class="p">:</span> <span class="no">LazySegmentTree</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="n">lazyValue</span> <span class="o">!=</span> <span class="mi">0</span> <span class="p">{</span>
            <span class="n">lson</span><span class="o">.</span><span class="n">lazyValue</span> <span class="o">+=</span> <span class="n">lazyValue</span>
            <span class="n">rson</span><span class="o">.</span><span class="n">lazyValue</span> <span class="o">+=</span> <span class="n">lazyValue</span>
            <span class="n">lson</span><span class="o">.</span><span class="n">value</span> <span class="o">+=</span> <span class="n">lazyValue</span> <span class="o">*</span> <span class="p">(</span><span class="n">round</span> <span class="o">-</span> <span class="p">(</span><span class="n">round</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="p">))</span>
            <span class="n">rson</span><span class="o">.</span><span class="n">value</span> <span class="o">+=</span> <span class="n">lazyValue</span> <span class="o">*</span> <span class="p">(</span><span class="n">round</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="p">)</span>
            <span class="n">lazyValue</span> <span class="o">=</span> <span class="mi">0</span>
        <span class="p">}</span>
    <span class="p">}</span>
    <span class="kp">public</span> <span class="n">init</span><span class="p">(</span><span class="ss">array</span><span class="p">:</span> <span class="o">[</span><span class="no">Int</span><span class="o">]</span><span class="p">,</span> <span class="ss">leftBound</span><span class="p">:</span> <span class="no">Int</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="no">Int</span><span class="p">)</span> <span class="p">{</span>
        <span class="nb">self</span><span class="o">.</span><span class="n">leftBound</span> <span class="o">=</span> <span class="n">leftBound</span>
        <span class="nb">self</span><span class="o">.</span><span class="n">rightBound</span> <span class="o">=</span> <span class="n">rightBound</span>
        <span class="nb">self</span><span class="o">.</span><span class="n">value</span> <span class="o">=</span> <span class="mi">0</span>
        <span class="nb">self</span><span class="o">.</span><span class="n">lazyValue</span> <span class="o">=</span> <span class="mi">0</span>
        <span class="k">if</span> <span class="n">leftBound</span> <span class="o">==</span> <span class="n">rightBound</span> <span class="p">{</span>
            <span class="n">value</span> <span class="o">=</span> <span class="n">array</span><span class="o">[</span><span class="n">leftBound</span><span class="o">]</span>
            <span class="k">return</span>
        <span class="p">}</span>
        <span class="n">let</span> <span class="n">middle</span> <span class="o">=</span> <span class="p">(</span><span class="n">leftBound</span> <span class="o">+</span> <span class="n">rightBound</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span>
        <span class="n">leftChild</span> <span class="o">=</span> <span class="no">LazySegmentTree</span><span class="p">(</span><span class="ss">array</span><span class="p">:</span> <span class="n">array</span><span class="p">,</span> <span class="ss">leftBound</span><span class="p">:</span> <span class="n">leftBound</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="n">middle</span><span class="p">)</span>
        <span class="n">rightChild</span> <span class="o">=</span> <span class="no">LazySegmentTree</span><span class="p">(</span><span class="ss">array</span><span class="p">:</span> <span class="n">array</span><span class="p">,</span> <span class="ss">leftBound</span><span class="p">:</span> <span class="n">middle</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="n">rightBound</span><span class="p">)</span>
        <span class="n">pushUp</span><span class="p">(</span><span class="ss">lson</span><span class="p">:</span> <span class="n">leftChild!</span><span class="p">,</span> <span class="ss">rson</span><span class="p">:</span> <span class="n">rightChild!</span><span class="p">)</span>
    <span class="p">}</span>
    <span class="kp">public</span> <span class="n">convenience</span> <span class="n">init</span><span class="p">(</span><span class="ss">array</span><span class="p">:</span> <span class="o">[</span><span class="no">Int</span><span class="o">]</span><span class="p">)</span> <span class="p">{</span>
        <span class="nb">self</span><span class="o">.</span><span class="n">init</span><span class="p">(</span><span class="ss">array</span><span class="p">:</span> <span class="n">array</span><span class="p">,</span> <span class="ss">leftBound</span><span class="p">:</span> <span class="mi">0</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="n">array</span><span class="o">.</span><span class="n">count</span> <span class="o">-</span> <span class="mi">1</span><span class="p">)</span>
    <span class="p">}</span>
    <span class="kp">public</span> <span class="n">func</span> <span class="n">query</span><span class="p">(</span><span class="ss">leftBound</span><span class="p">:</span> <span class="no">Int</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="no">Int</span><span class="p">)</span> <span class="o">-&gt;</span> <span class="no">Int</span> <span class="p">{</span>
        <span class="k">if</span> <span class="n">leftBound</span> <span class="o">&lt;=</span> <span class="nb">self</span><span class="o">.</span><span class="n">leftBound</span> <span class="o">&amp;&amp;</span> <span class="nb">self</span><span class="o">.</span><span class="n">rightBound</span> <span class="o">&lt;=</span> <span class="n">rightBound</span> <span class="p">{</span>
            <span class="k">return</span> <span class="n">value</span>
        <span class="p">}</span>
        <span class="n">guard</span> <span class="n">let</span> <span class="n">leftChild</span>  <span class="o">=</span> <span class="n">leftChild</span>  <span class="k">else</span> <span class="p">{</span> <span class="n">fatalError</span><span class="p">(</span><span class="s2">&quot;leftChild should not be nil&quot;</span><span class="p">)</span> <span class="p">}</span>
        <span class="n">guard</span> <span class="n">let</span> <span class="n">rightChild</span> <span class="o">=</span> <span class="n">rightChild</span> <span class="k">else</span> <span class="p">{</span> <span class="n">fatalError</span><span class="p">(</span><span class="s2">&quot;rightChild should not be nil&quot;</span><span class="p">)</span> <span class="p">}</span>
        <span class="n">pushDown</span><span class="p">(</span><span class="ss">round</span><span class="p">:</span> <span class="nb">self</span><span class="o">.</span><span class="n">rightBound</span> <span class="o">-</span> <span class="nb">self</span><span class="o">.</span><span class="n">leftBound</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="ss">lson</span><span class="p">:</span> <span class="n">leftChild</span><span class="p">,</span> <span class="ss">rson</span><span class="p">:</span> <span class="n">rightChild</span><span class="p">)</span>
        <span class="n">let</span> <span class="n">middle</span> <span class="o">=</span> <span class="p">(</span><span class="nb">self</span><span class="o">.</span><span class="n">leftBound</span> <span class="o">+</span> <span class="nb">self</span><span class="o">.</span><span class="n">rightBound</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span>
        <span class="n">var</span> <span class="ss">result</span><span class="p">:</span> <span class="no">Int</span> <span class="o">=</span> <span class="mi">0</span>
        <span class="k">if</span> <span class="n">leftBound</span> <span class="o">&lt;=</span> <span class="n">middle</span> <span class="p">{</span> <span class="n">result</span> <span class="o">+=</span>  <span class="n">leftChild</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="ss">leftBound</span><span class="p">:</span> <span class="n">leftBound</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="n">rightBound</span><span class="p">)</span> <span class="p">}</span>
        <span class="k">if</span> <span class="n">rightBound</span> <span class="o">&gt;</span> <span class="n">middle</span> <span class="p">{</span> <span class="n">result</span> <span class="o">+=</span> <span class="n">rightChild</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="ss">leftBound</span><span class="p">:</span> <span class="n">leftBound</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="n">rightBound</span><span class="p">)</span> <span class="p">}</span>
        <span class="k">return</span> <span class="n">result</span>
    <span class="p">}</span>
    <span class="sr">//</span> <span class="ss">MARK</span><span class="p">:</span> <span class="o">-</span> <span class="no">One</span> <span class="no">Item</span> <span class="no">Update</span>
    <span class="kp">public</span> <span class="n">func</span> <span class="n">update</span><span class="p">(</span><span class="ss">index</span><span class="p">:</span> <span class="no">Int</span><span class="p">,</span> <span class="ss">incremental</span><span class="p">:</span> <span class="no">Int</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="nb">self</span><span class="o">.</span><span class="n">leftBound</span> <span class="o">==</span> <span class="nb">self</span><span class="o">.</span><span class="n">rightBound</span> <span class="p">{</span>
            <span class="nb">self</span><span class="o">.</span><span class="n">value</span> <span class="o">+=</span> <span class="n">incremental</span>
            <span class="k">return</span>
        <span class="p">}</span>
        <span class="n">guard</span> <span class="n">let</span> <span class="n">leftChild</span>  <span class="o">=</span> <span class="n">leftChild</span>  <span class="k">else</span> <span class="p">{</span> <span class="n">fatalError</span><span class="p">(</span><span class="s2">&quot;leftChild should not be nil&quot;</span><span class="p">)</span> <span class="p">}</span>
        <span class="n">guard</span> <span class="n">let</span> <span class="n">rightChild</span> <span class="o">=</span> <span class="n">rightChild</span> <span class="k">else</span> <span class="p">{</span> <span class="n">fatalError</span><span class="p">(</span><span class="s2">&quot;rightChild should not be nil&quot;</span><span class="p">)</span> <span class="p">}</span>
        <span class="n">let</span> <span class="n">middle</span> <span class="o">=</span> <span class="p">(</span><span class="nb">self</span><span class="o">.</span><span class="n">leftBound</span> <span class="o">+</span> <span class="nb">self</span><span class="o">.</span><span class="n">rightBound</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span>
        <span class="k">if</span> <span class="n">index</span> <span class="o">&lt;=</span> <span class="n">middle</span> <span class="p">{</span> <span class="n">leftChild</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="ss">index</span><span class="p">:</span> <span class="n">index</span><span class="p">,</span> <span class="ss">incremental</span><span class="p">:</span> <span class="n">incremental</span><span class="p">)</span> <span class="p">}</span>
        <span class="k">else</span> <span class="p">{</span> <span class="n">rightChild</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="ss">index</span><span class="p">:</span> <span class="n">index</span><span class="p">,</span> <span class="ss">incremental</span><span class="p">:</span> <span class="n">incremental</span><span class="p">)</span> <span class="p">}</span>
        <span class="n">pushUp</span><span class="p">(</span><span class="ss">lson</span><span class="p">:</span> <span class="n">leftChild</span><span class="p">,</span> <span class="ss">rson</span><span class="p">:</span> <span class="n">rightChild</span><span class="p">)</span>
    <span class="p">}</span>
    <span class="sr">//</span> <span class="ss">MARK</span><span class="p">:</span> <span class="o">-</span> <span class="no">Interval</span> <span class="no">Item</span> <span class="no">Update</span>
    <span class="kp">public</span> <span class="n">func</span> <span class="n">update</span><span class="p">(</span><span class="ss">leftBound</span><span class="p">:</span> <span class="no">Int</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="no">Int</span><span class="p">,</span> <span class="ss">incremental</span><span class="p">:</span> <span class="no">Int</span><span class="p">)</span> <span class="p">{</span>
        <span class="k">if</span> <span class="n">leftBound</span> <span class="o">&lt;=</span> <span class="nb">self</span><span class="o">.</span><span class="n">leftBound</span> <span class="o">&amp;&amp;</span> <span class="nb">self</span><span class="o">.</span><span class="n">rightBound</span> <span class="o">&lt;=</span> <span class="n">rightBound</span> <span class="p">{</span>
            <span class="nb">self</span><span class="o">.</span><span class="n">lazyValue</span> <span class="o">+=</span> <span class="n">incremental</span>
            <span class="nb">self</span><span class="o">.</span><span class="n">value</span> <span class="o">+=</span> <span class="n">incremental</span> <span class="o">*</span> <span class="p">(</span><span class="nb">self</span><span class="o">.</span><span class="n">rightBound</span> <span class="o">-</span> <span class="nb">self</span><span class="o">.</span><span class="n">leftBound</span> <span class="o">+</span> <span class="mi">1</span><span class="p">)</span>
            <span class="k">return</span> 
        <span class="p">}</span>
        <span class="n">guard</span> <span class="n">let</span> <span class="n">leftChild</span> <span class="o">=</span> <span class="n">leftChild</span> <span class="k">else</span> <span class="p">{</span> <span class="n">fatalError</span><span class="p">()</span> <span class="p">}</span>
        <span class="n">guard</span> <span class="n">let</span> <span class="n">rightChild</span> <span class="o">=</span> <span class="n">rightChild</span> <span class="k">else</span> <span class="p">{</span> <span class="n">fatalError</span><span class="p">()</span> <span class="p">}</span>
        <span class="n">pushDown</span><span class="p">(</span><span class="ss">round</span><span class="p">:</span> <span class="nb">self</span><span class="o">.</span><span class="n">rightBound</span> <span class="o">-</span> <span class="nb">self</span><span class="o">.</span><span class="n">leftBound</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="ss">lson</span><span class="p">:</span> <span class="n">leftChild</span><span class="p">,</span> <span class="ss">rson</span><span class="p">:</span> <span class="n">rightChild</span><span class="p">)</span>
        <span class="n">let</span> <span class="n">middle</span> <span class="o">=</span> <span class="p">(</span><span class="nb">self</span><span class="o">.</span><span class="n">leftBound</span> <span class="o">+</span> <span class="nb">self</span><span class="o">.</span><span class="n">rightBound</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span>
        <span class="k">if</span> <span class="n">leftBound</span> <span class="o">&lt;=</span> <span class="n">middle</span> <span class="p">{</span> <span class="n">leftChild</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="ss">leftBound</span><span class="p">:</span> <span class="n">leftBound</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="n">rightBound</span><span class="p">,</span> <span class="ss">incremental</span><span class="p">:</span> <span class="n">incremental</span><span class="p">)</span> <span class="p">}</span>
        <span class="k">if</span> <span class="n">middle</span> <span class="o">&lt;</span> <span class="n">rightBound</span> <span class="p">{</span> <span class="n">rightChild</span><span class="o">.</span><span class="n">update</span><span class="p">(</span><span class="ss">leftBound</span><span class="p">:</span> <span class="n">leftBound</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="n">rightBound</span><span class="p">,</span> <span class="ss">incremental</span><span class="p">:</span> <span class="n">incremental</span><span class="p">)</span> <span class="p">}</span>
        <span class="n">pushUp</span><span class="p">(</span><span class="ss">lson</span><span class="p">:</span> <span class="n">leftChild</span><span class="p">,</span> <span class="ss">rson</span><span class="p">:</span> <span class="n">rightChild</span><span class="p">)</span>
    <span class="p">}</span>
<span class="p">}</span></code></pre></div>
<p>我们来解释一下这些代码片段：</p>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="kp">private</span> <span class="n">var</span> <span class="ss">lazyValue</span><span class="p">:</span> <span class="no">Int</span></code></pre></div>
<p>这里我们增加了一个 <code>lazyValue</code> 变量，这个变量的含义在当前数据结构中是当前节点需要的增量。因为其 <code>update</code> 操作时用来对指定元素和指定范围的所有元素进行数量的增减。<code>lazyValue</code> 的值弱不为0，则说明当前节点的 <code>value</code> 需要更新，而其真值为 <code>value + lazyValue * (rightBound - leftBound + 1)</code>。</p>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="sr">//</span> <span class="ss">MARK</span><span class="p">:</span> <span class="o">-</span> <span class="no">Push</span> <span class="no">Down</span> <span class="no">Operation</span>
<span class="sr">//</span> <span class="ss">Description</span><span class="p">:</span> <span class="err">这里是</span> <span class="n">push</span> <span class="n">down</span> <span class="err">操作，用来对</span> <span class="no">Segment</span> <span class="no">Tree</span> <span class="err">向下更新</span>
<span class="sr">//</span> <span class="no">Open</span> <span class="no">Interface</span> <span class="ss">Function</span><span class="p">:</span> <span class="err">此处应该开放方法对齐进行</span> <span class="no">Override</span>
<span class="kp">private</span> <span class="n">func</span> <span class="n">pushDown</span><span class="p">(</span><span class="ss">round</span><span class="p">:</span> <span class="no">Int</span><span class="p">,</span> <span class="ss">lson</span><span class="p">:</span> <span class="no">LazySegmentTree</span><span class="p">,</span> <span class="ss">rson</span><span class="p">:</span> <span class="no">LazySegmentTree</span><span class="p">)</span> <span class="p">{</span>
    <span class="k">if</span> <span class="n">lazyValue</span> <span class="o">!=</span> <span class="mi">0</span> <span class="p">{</span>
        <span class="n">lson</span><span class="o">.</span><span class="n">lazyValue</span> <span class="o">+=</span> <span class="n">lazyValue</span>
        <span class="n">rson</span><span class="o">.</span><span class="n">lazyValue</span> <span class="o">+=</span> <span class="n">lazyValue</span>
        <span class="n">lson</span><span class="o">.</span><span class="n">value</span> <span class="o">+=</span> <span class="n">lazyValue</span> <span class="o">*</span> <span class="p">(</span><span class="n">round</span> <span class="o">-</span> <span class="p">(</span><span class="n">round</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="p">))</span>
        <span class="n">rson</span><span class="o">.</span><span class="n">value</span> <span class="o">+=</span> <span class="n">lazyValue</span> <span class="o">*</span> <span class="p">(</span><span class="n">round</span> <span class="o">&gt;&gt;</span> <span class="mi">1</span><span class="p">)</span>
        <span class="n">lazyValue</span> <span class="o">=</span> <span class="mi">0</span>
    <span class="p">}</span>
<span class="p">}</span></code></pre></div>
<p><img src="../assets/images/blog/15034809922428/pushdown.png" alt="pushdown" /></p>
<p>这块代码主要是检查当前节点是否需要更新，如果 <code>lazyValue</code> 的值不为 0，则需要向下更新一次。其更新原则就是左右范围差值算出元素个数，乘以增量算出父亲节点的增量，之后更新子节点的增量值，最后清零自身增量值。</p>
<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="kp">public</span> <span class="n">func</span> <span class="n">query</span><span class="p">(</span><span class="ss">leftBound</span><span class="p">:</span> <span class="no">Int</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="no">Int</span><span class="p">)</span> <span class="o">-&gt;</span> <span class="no">Int</span> <span class="p">{</span>
    <span class="k">if</span> <span class="n">leftBound</span> <span class="o">&lt;=</span> <span class="nb">self</span><span class="o">.</span><span class="n">leftBound</span> <span class="o">&amp;&amp;</span> <span class="nb">self</span><span class="o">.</span><span class="n">rightBound</span> <span class="o">&lt;=</span> <span class="n">rightBound</span> <span class="p">{</span>
        <span class="k">return</span> <span class="n">value</span>
    <span class="p">}</span>
    <span class="n">guard</span> <span class="n">let</span> <span class="n">leftChild</span>  <span class="o">=</span> <span class="n">leftChild</span>  <span class="k">else</span> <span class="p">{</span> <span class="n">fatalError</span><span class="p">(</span><span class="s2">&quot;leftChild should not be nil&quot;</span><span class="p">)</span> <span class="p">}</span>
    <span class="n">guard</span> <span class="n">let</span> <span class="n">rightChild</span> <span class="o">=</span> <span class="n">rightChild</span> <span class="k">else</span> <span class="p">{</span> <span class="n">fatalError</span><span class="p">(</span><span class="s2">&quot;rightChild should not be nil&quot;</span><span class="p">)</span> <span class="p">}</span>
    <span class="n">pushDown</span><span class="p">(</span><span class="ss">round</span><span class="p">:</span> <span class="nb">self</span><span class="o">.</span><span class="n">rightBound</span> <span class="o">-</span> <span class="nb">self</span><span class="o">.</span><span class="n">leftBound</span> <span class="o">+</span> <span class="mi">1</span><span class="p">,</span> <span class="ss">lson</span><span class="p">:</span> <span class="n">leftChild</span><span class="p">,</span> <span class="ss">rson</span><span class="p">:</span> <span class="n">rightChild</span><span class="p">)</span>
    <span class="n">let</span> <span class="n">middle</span> <span class="o">=</span> <span class="p">(</span><span class="nb">self</span><span class="o">.</span><span class="n">leftBound</span> <span class="o">+</span> <span class="nb">self</span><span class="o">.</span><span class="n">rightBound</span><span class="p">)</span> <span class="o">/</span> <span class="mi">2</span>
    <span class="n">var</span> <span class="ss">result</span><span class="p">:</span> <span class="no">Int</span> <span class="o">=</span> <span class="mi">0</span>
    <span class="k">if</span> <span class="n">leftBound</span> <span class="o">&lt;=</span> <span class="n">middle</span> <span class="p">{</span> <span class="n">result</span> <span class="o">+=</span>  <span class="n">leftChild</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="ss">leftBound</span><span class="p">:</span> <span class="n">leftBound</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="n">rightBound</span><span class="p">)</span> <span class="p">}</span>
    <span class="k">if</span> <span class="n">rightBound</span> <span class="o">&gt;</span> <span class="n">middle</span> <span class="p">{</span> <span class="n">result</span> <span class="o">+=</span> <span class="n">rightChild</span><span class="o">.</span><span class="n">query</span><span class="p">(</span><span class="ss">leftBound</span><span class="p">:</span> <span class="n">leftBound</span><span class="p">,</span> <span class="ss">rightBound</span><span class="p">:</span> <span class="n">rightBound</span><span class="p">)</span> <span class="p">}</span>
    <span class="k">return</span> <span class="n">result</span>
<span class="p">}</span></code></pre></div>
<p>根据前文的分析，当对区间进行查询的时候，我们就调用一次 <code>pushDown</code> 来向下更新数据，以保证在递归查询之前所有的数据处于最新状态。有的读者可能有疑问，为什么这里的代码比原版的少了一个 <code>if else</code> 的判断？因为我使用的是判断中值与边界的关系，而不是边界与边界的关系。笔者认为这么判断代码会更加简洁，思路也会更加清晰。</p>
<p>以上便是 <strong>lazy</strong> 思想实现线段树的区间更新操作及思路。作为线段树的扩展，还可以通过<strong>可持久化线段树</strong>（也称<strong>主席树</strong>）对于永久化保存状态的概念，更深一步的理解 <strong>lazy</strong> 思想。另外，在代码实现的时候，<strong>notonlysuccess</strong>大牛的实例代码，可以说是线段树中最为清晰的实现方式，给出<a href="http://www.cnblogs.com/Destiny-Gem/articles/3875243.html">链接</a>有兴趣可以自行学习。</p>
<h2 id="section">后记</h2>
<p>线段树在工程项目中是一科极少出现的数据结构，由于它属于区间树（Interval Tree）的（而且是一种大开销的）一种实现，所以更多的用来解决数学中的区间问题和统计问题中。在之后的完善中，还会针对于 <code>SumSegmentTree</code> 增加更多的区间（交、并、补）等操作，以及叶子节点合并、二维线段树等等更为复杂，希望大家共同学习，一起完善 <strong>Segment Tree In Swift</strong> 🐦。</p>
<blockquote>
  <p>文章最后求一个中译英的译者，一起向 <code>swift-algorithm-club</code> 进行 contribution。</p>
</blockquote>
  <footer class="post-footer">
    <section class="author">
      <h4>Desgard_Duan</h4>
      <p>I write many code to write less code.💻</p>
    </section>
<aside class="share">
  <h4>Share this.</h4>
  <a href="http://twitter.com/share?text=《用 Lazy 思想实现 Segment Tree 的区间更新》 -- Guardia · 瓜地&amp;url=https://www.desgard.com/lazy-segment-tree/"
  onclick="window.open(this.href, 'twitter-share', 'width=550,height=235');return false;">
    <i class="fa fa-twitter-square"></i>
  </a>
  <a href="http://v.t.sina.com.cn/share/share.php?url=https://www.desgard.com/lazy-segment-tree/&amp;title=《用 Lazy 思想实现 Segment Tree 的区间更新》 —— Guardia · 瓜地" onclick="window.open(this.href, 'twitter-share', 'width=550,height=235');return false;">
    <i class="fa fa-weibo"></i>
  </a>
</aside>
      <hr>
<aside id="comments" class="disqus">
  <div id="container"></div>
  <!-- <link rel="stylesheet" href="/assets/css/gitment.css">
  <script src="https://imsun.github.io/gitment/dist/gitment.browser.js"></script>
  <script>
  var gitment = new Gitment({
    id: "https://www.desgard.com/lazy-segment-tree/", 
    owner: 'Desgard',
    repo: 'desgard.github.com',
    oauth: {
      client_id: 'e2612df42f3f2a83e71c',
      client_secret: 'b53e85b314bb24a6d06773e48bbb62a4de3b8b3a',
    },
  })
  gitment.render('container')
  </script> -->
<link rel="stylesheet" href="/assets/css/gitalk.css">
<script src="https://unpkg.com/gitalk/dist/gitalk.min.js"></script>
<div id='gitalk-container'></div>
<script>
    const gitalk = new Gitalk({
        id: "https://www.desgard.com/lazy-segment-tree/", 
        clientID: 'e2612df42f3f2a83e71c',
        clientSecret: 'b53e85b314bb24a6d06773e48bbb62a4de3b8b3a',
        repo: 'desgard.github.com',
        owner: 'Desgard',
        admin: ['Desgard'],
        // facebook-like distraction free mode
        distractionFreeMode: false
    })
    gitalk.render('gitalk-container')
</script>
</aside>
  </footer>
</article>
    </main>
<footer class="footer">
  <div class="container">
    <ul class="icons">
      <li>
        <a href="https://github.com/desgard" class="icon-github" target="_blank">
          <i class="fa fa-github"></i>
        </a>
      </li>
      <li>
        <a href="https://www.facebook.com/desgard.duan" class="icon-facebook" target="_blank">
          <i class="fa fa-facebook"></i>
        </a>
      </li>
      <li>
        <a href="https://twitter.com/Desgard_Duan" class="icon-twitter" target="_blank">
          <i class="fa fa-twitter"></i>
        </a>
      </li>
      <li>
        <a href="https://stackoverflow.com/users/6119149/desgard-duan" class="icon-github" target="_blank">
          <i class="fa fa-stack-overflow"></i>
        </a>
      </li>
      <li>
        <a href="https://weibo.com/desgard" class="icon-instagram" target="_blank">
          <i class="fa fa-weibo"></i>
        </a>
      </li>
    </ul>
    <p>
      <q>I write many code to write less code.💻</q>
      <small>– Gua</small>
    </p>
    <small class="clearfix">
      Powered by <a href="http://jekyllrb.com" target="_blank">Jekyll</a> • <a href="https://github.com/desgard" target="_blank">Open source <i class="fa fa-heart"></i></a>
    </small>
  </div>
</footer>
<a class="scroll-up fa fa-chevron-up bounce" href="#" data-position="0"></a>
<div id="modalSearch" class="modal">
  <div class="modal__overlay"></div>
  <div class="modal__content">
    <a href="#!" class="modal-close" data-modal-close>&times;</a>
    <div class="search-container">
      <input type="text" id="search-input" placeholder="Search articles">
      <ul id="results-container"></ul>
    </div>
  </div>
</div>
    <script src="/assets/main-52d417e8a6ff9f5b168386d37c96338a.js"></script>
  </body>
  <script>
    var link = "" ;
    var os = function() {  
      var ua = navigator.userAgent,  
      isWindowsPhone = /(?:Windows Phone)/.test(ua),  
      isSymbian = /(?:SymbianOS)/.test(ua) || isWindowsPhone,   
      isAndroid = /(?:Android)/.test(ua),   
      isFireFox = /(?:Firefox)/.test(ua),   
      isChrome = /(?:Chrome|CriOS)/.test(ua),  
      isTablet = /(?:iPad|PlayBook)/.test(ua) || (isAndroid && !/(?:Mobile)/.test(ua)) || (isFireFox && /(?:Tablet)/.test(ua)),  
      isPhone = /(?:iPhone)/.test(ua) && !isTablet,  
      isPc = !isPhone && !isAndroid && !isSymbian;  
      return {  
        isTablet: isTablet,  
        isPhone: isPhone,  
        isAndroid : isAndroid,  
        isPc : isPc  
      };  
    }();  
    if (link.length > 0) {
      if (os.isAndroid || os.isPhone) {
        location.replace(link);
      }
    }
  </script>
</html>